package 程序员面试金典;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 面试题 08.02. 迷路的机器人
 * 设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。
 *
 *
 *
 * 网格中的障碍物和空位置分别用 1 和 0 来表示。
 *
 * 返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径，返回空数组。
 *
 * 示例 1:
 *
 * 输入:
 * [
 *   [0,0,0],
 *   [0,1,0],
 *   [0,0,0]
 * ]
 * 输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]
 * 解释:
 * 输入中标粗的位置即为输出表示的路径，即
 * 0行0列（左上角） -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列（右下角）
 * 说明：r 和 c 的值均不超过 100。
 */
public class T08_02 {

    List<List<Integer>> path = new LinkedList<>();  // 记录路径

    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {

        boolean dfs = dfs(obstacleGrid, new int[]{0, 0});

        return path;

    }

    //递归回溯
    public boolean dfs(int[][] obstacleGrid, int[] currIndex) {
        //判断当前的坐标 是否合法 curr[0] 行标  curr[1] 列标 obs[0].length 列宽 obs.length 行数

        if (currIndex[0] < 0 || currIndex[0] >= obstacleGrid.length || currIndex[1] < 0 || currIndex[1] >= obstacleGrid[0].length) {
            return false;
        }

        //地址合法  判断是否为障碍物 或者已经访问过
        if (obstacleGrid[currIndex[0]][currIndex[1]] == 1 || obstacleGrid[currIndex[0]][currIndex[1]] == 2) {
            return false;
        }

        path.add(Arrays.asList(currIndex[0], currIndex[1]));
        //将此位置 标记为2 表示已经访问过
        obstacleGrid[currIndex[0]][currIndex[1]] = 2;
        //是否到达终点
        if (currIndex[0] == obstacleGrid.length - 1 && currIndex[1] == obstacleGrid[0].length - 1) {
            return true;
        }

        //将下 右 进行递归 判断是否可达
        boolean downResult = dfs(obstacleGrid, new int[]{currIndex[0] + 1, currIndex[1]});
        boolean rightResult = dfs(obstacleGrid, new int[]{currIndex[0], currIndex[1] + 1});
        if (downResult || rightResult) {
            return true;
        }

        //说明这个路径不通 撤销选择
        path.remove(path.size() - 1);

        return false;

    }
}
